package com.gxc.string;

/**
 * 2734. 执行子串操作后的字典序最小字符串
 * 给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：
 *
 * 选择 s 的任一非空子字符串，可能是整个字符串，
 * 接着将字符串中的每一个字符替换为英文字母表中的前一个字符。
 * 例如，'b' 用 'a' 替换，'a' 用 'z' 替换。
 * 返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。
 *
 * 子字符串 是字符串中的一个连续字符序列。
 *
 * 现有长度相同的两个字符串 x 和 字符串 y ，
 * 在满足 x[i] != y[i] 的第一个位置 i 上，
 * 如果  x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。
 */
public class SmallestString {

    public static void main(String[] args) {
        System.out.println(handle("cbabc"));
        System.out.println(handle("acbbc"));
        System.out.println(handle("leetcode"));
        System.out.println(handle("aa"));

        char a = 'b';
        System.out.println(a- 1);
    }

    //贪心
    public static String handle(String s) {
        if (s.length()==0) return "";
        int n = s.length();
        boolean isA = true;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != 'a') {
                isA = false;
                break;
            }
        }
        if (isA) {
            return s.substring(0, n-1) + "z";
        }

        Character[] characters = new Character[] {'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y'};

        boolean flag = false;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != 'a' && !flag) {
                flag = true;
                while (i<n && s.charAt(i) != 'a') {
                    sb.append(characters[s.charAt(i) - 'a']);
                    i++;
                }
                if (i<n) sb.append(s.charAt(i));
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

    /**
     * 我们要找到第一个非 ‘a’ 字符，将它作为非空子字符串的开始下标。
     * 在这之后，再找到第一个 ‘a’ 字符，将它作为非空子字符串的结束下标（不包含），
     * 这之间所有的字符，都做一次替换，就得到了目标字符串。
     *
     * 还有一种可能是，字符串为全 ‘a’，
     * 这种情况下我们找不到第一个非 ‘a’ 字符，
     * 题目有要求必须进行一次替换且子字符串非空，
     * 这种情况下我们对末尾字符进行一次替换即可。
     *
     * 用return中断循环
     */
    class Solution {
        public String smallestString(String S) {
            char[] s = S.toCharArray();
            int n = s.length;
            for (int i = 0; i < n; i++) {
                if (s[i] > 'a') {
                    // 继续向后遍历
                    for (; i < n && s[i] > 'a'; i++) {
                        s[i]--;
                    }
                    return new String(s);
                }
            }
            // 所有字母均为 a
            s[n - 1] = 'z';
            return new String(s);
        }
    }

}
